package 算法.排序.快速排序;

import com.sun.org.apache.regexp.internal.recompile;

import sun.security.util.Length;
import util.SortUtil;

/**
 * 【三向切分快速排序】
 * 		实际应用中经常会出现大量重复元素的排序情况，而快速排序在面对重复元素时排序复杂度并没有降低。
 * Dijkstra提出的三向切分快速排序方法可以迅速降低这种情况下的复杂度，甚至有可能达到线性级别n，
 * 如荷兰国旗问题（见我的另一篇文章）。
 * 其基本思想就是
 * 选取切分点v，从左到右遍历，
 * 维护一个从前往后遍历的位置点lt，使得a[0]~a[lt-1]都小于v，
 * 维护一个从前往后遍历的位置点i，使得a[lt]~a[i-1]都等于v，
 * 维护一个从后往前的位置点，使得a[i]~a[gt]都大于v。
 * lo..lt..gt..hi
 * TODO: 尚未测试。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
 * @Date 2017-09-12 00：30
 * @author Administrator
 * @version
 */
public class Quick3 {
	
	public void sort(int[] arr, int lo, int hi) {
		if (lo >= hi)	return;
		int lt = lo, i = lo+1, gt = hi;
		int v = arr[lo];
		while (i < gt) {
			int comp = compareTo(arr, v, arr[i]);
			if (comp < 0)		exch(arr, lt++, i++);
			else if (comp > 0) 	exch(arr, gt--, i);
			else i++;
		}
		sort(arr, lo, lt-1);
		sort(arr, gt+1, hi);
	}
	
	private int compareTo(int[] arr, int a, int b) {
		if (a < b)			return -1;
		else if (a > b)		return 1;
		return 0;
	}
	
	private void exch(int[] arr, int a, int b) {
		int t = arr[a];
		arr[a] = arr[b];
		arr[b] = t;
	}
	
	public static void main(String[] args) {
		Quick3 quickSort = new Quick3();
		int[] arr = SortUtil.getInitDisorderArr();
		quickSort.sort(arr, 0, arr.length - 1);
	}
}
